#ifndef __DAT_H__
#define __DAT_H__
#ifndef __SORT_H__
#define __SORT_H__
#include<stdio.h>
#include<stdlib.h>
#include"dat.h"
#include"sort.h"

extern sqlist list;


void insert_sort1(sqlist* l){
	int i,j;
	for(i=2;i<=l->length;i++){
		l->r[0]=l->r[i];
		for(j=i-1;j>=1&&cmp(l,j,0)>0;j--)
			l->r[j+1]=l->r[j];
		l->r[j+1]=l->r[0];
	}
}
void insert_sortb(sqlist* l){
	int i,j,low,high,mid;
	for(i=2;i<=l->length;++i){
		l->r[0]=l->r[i];
		low=1;
		high=i-1;
		while(low<=high){
			mid=(low+high)/2;
			if(cmp(l,mid,0)>0)high=mid-1;
			else low=mid+1;
		}
		for(j=i-1;j>=high+1;--j)
			l->r[j+1]=l->r[j];
		l->r[high+1]=l->r[0];
	}
}
void shell_insert(sqlist* l,int dk){
	int i,j;
	for(i=dk+1;i<=l->length;++i)
	{
		l->r[0]=l->r[i];
		for(j=i-dk;j>=1&&cmp(l,j,0)>0;j=j-dk)
			l->r[j+dk]=l->r[j];
		l->r[j+dk]=l->r[0];
	}
}
void insert_sort_shell(sqlist* l){
	int dlta[3]={5,3,1};
	for(int k=0;k<3;++k)
	{
		shell_insert(l,dlta[k]);
	}
}
void switch_sort1(sqlist*l){
	int i,j;
	for(i=1;i<l->length;++i){
		for(j=1;j<l->length+1-i;++j){
			if(cmp(l,j,j+1)>0){
				swap(l,j,j+1);
			}
		}
	}

}
void quick_sort(sqlist*l,int low,int high){
	int left=low,right=high;
	if(left>=right)return;
	l->r[0]=l->r[left];
	while(left<right){
		while(left<right&&cmp(l,right,0)>=0)--right;
		l->r[left]=l->r[right];
		while(left<right&&cmp(l,left,0)<0)++left;
		l->r[right]=l->r[left];
	}
	l->r[left]=l->r[0];
	quick_sort(l,low,left-1);
	quick_sort(l,left+1,high);
}
void switch_sort_quick(sqlist*l){
	quick_sort(l,1,l->length);	
}
void select_sort1(sqlist*l){
	for(int i=1;i<l->length;i++){
 		int min=i;
        for(int j=i;j<l->length+1;j++){
			if(cmp(l,min,j)>0)min=j;	
        }
		swap(l,i,min);
	}
}
void heapadjust_min(sqlist* l,int s,int m){
	l->r[0]=l->r[s];
	for(int j=2*s;j<=m;j*=2){
		if(j<m&&cmp(l,j,j+1)>0)++j;
		if(cmp(l,0,j)<=0)break;
		l->r[s]=l->r[j];
		s=j;
	}
	l->r[s]=l->r[0];
}
void heapadjust_max(sqlist* l,int s,int m){
	l->r[0]=l->r[s];
	for(int j=2*s;j<=m;j*=2){
		if(j<m&&cmp(l,j,j+1)<0)++j;
		if(cmp(l,0,j)>=0)break;
		l->r[s]=l->r[j];
		s=j;
	}
	l->r[s]=l->r[0];
}
void select_sort_heap(sqlist* l){
	//1.construct a heap
	for(int i=l->length/2;i>=1;--i){
		heapadjust_max(l,i,l->length);
	}
	print_list_key(&list);
	//2.ajust the heap
	for(int i=l->length;i>1;i--){
		swap(l,1,i);
		heapadjust_max(l,1,i-1);
	}
}
void merge(redtype* arr,redtype* swap_arr,int left,int mid,int right){
	int i=left,j=mid,idx=left;
	while(i<mid&&j<right){
		if(cmp_redtype(arr[i],arr[j])<0){
			swap_arr[idx++]=arr[i++];
		}else{
			swap_arr[idx++]=arr[j++];
		}
	}
	while(i<mid){
		swap_arr[idx++]=arr[i++];
	}
	while(j<right){
		swap_arr[idx++]=arr[j++];
	}
	for(int k=left;k<idx;k++){
		arr[k]=swap_arr[k];
	}
}
void do_merge_sort(redtype* arr,redtype* swap_arr,int left,int right){
	if(right-left<=1){
		return;
	}
	int mid=(left+right)/2;
	do_merge_sort(arr,swap_arr,left,mid);
	do_merge_sort(arr,swap_arr,mid,right);
	merge(arr,swap_arr,left,mid,right);
}
void merge_sort(sqlist* l){
	redtype *swap_arr;
	swap_arr=(redtype*)malloc(sizeof(redtype)*(l->length+1));
	do_merge_sort(l->r,swap_arr,1,l->length+1);
	free(swap_arr);
}

void list_test(){
    init_list();
    print_list_key(&list);
//	insert_sort1(&list);
	//insert_sortb(&list);
	//insert_sort_shell(&list);	
	//switch_sort1(&list);
	//switch_sort_quick(&list);
	//select_sort1(&list);
	//select_sort_heap(&list);
	merge_sort(&list);
    print_list_key(&list);
}
#endif
#endif
